Q1. Stack 是什麼

• 一種資料結構的概念，假設有一個容器是裝馬克杯的盒子 (這個盒子下面是封死的，無法拿東西)

  • 

• 現在第一步有小明、小美、小雅的馬克杯，依序被放入盒子中

  • 

• 課間小 Q&A： 你現在要從盒子中取出一個馬克杯，請問你會拿到誰的馬克杯 ?

• ANS：盒子內的杯子排序預期是如下圖，所以你從盒子取，只能拿到最上面的杯子，也就是小雅的杯子

  • 

• 也就是說，這種 Stack 概念，最後放的杯子，會最先拿起來，最早放的杯子，會被墊在最下面，最後才能拿到，也就是「先進後出」「後進先出」的概念 ( 英文稱為 Last-In-First-Out )

Q2. 所以學會 Stack 概念可以做什麼 ?

• 需要紀錄狀態，並且「先拿」「最後一個」狀態的時候，例如：
  • 瀏覽器的「回到上一頁」，他就跳到你上一步最後瀏覽的網頁
  • word 的 ctrl + Z 的復原鍵
  • 你要設計一隻會走迷宮的機器人，你希望他遇到分岔路，都能記錄狀態，當機器人走到死路，就回到上一次遇到的交叉路，最終就能找到出口
    • 

Lab. 明天要解的題目：20. Valid Parentheses

題目連結：https://leetcode.com/problems/valid-parentheses/
題目敘述：

• 你需要判斷是不是正常括號表示方式

  • 例如 ( 就要用 ) 作為閉合，不能使用 } 跟 ]

• 你需要判斷他是不是正常的方式閉合

  • 例如 ([)]，這種閉合方式就會錯誤

• 

• 測資的 Input/Output

  • 你會收到一個 s 變數的字串，s 會包含你要處理的字串
  • 最終你需要處理，s 字串是不是符合題目的規定，並回傳 True或False

• 

• 題目的條件

  • 變數 s 至少會有一個字元，最長為 10000
  • s 變數中只會出現有 ()[]{} 這樣的字元
    • 代表連空格都不會出現，所以你不能寫 ( ) [ ] { }

• 

• 看完題目，你要思考：

  • 如果 ([)] 是錯誤的，那什麼是正確的 ?
    • 你寫 ()[] 或 [()] 或 ([]) 是不是都可以 ?
  • 在小學數學運算中，{}是大括號，[]是中括號，()是小括號，優先順序為小括號 > 中括號 > 大括號，那這一個題目，遇到 ([{}]) 這樣的情況，是不是也是可接受的 ?

• 明天會分析該題 python 不同解法的優點，希望大家今天可以多先自己想一下這題 Stack 題如果是你，你的思考邏輯是什麼?